package com.wfm.leetcode.editor.cn;

import com.wfm.common.ListNode;

/**
 * 合并零之间的节点
 * 2025-03-26 15:08:13
 * 我们从链表头节点 head 的下一个节点开始遍历，并使用一个变量 total 维护当前遍历到的节点的元素之和。
 * 如果当前节点的值为 0，那么我们就新建一个值为 total 的节点，放在答案链表的尾部，
 * 并将 total 置零，否则我们将值累加进 total 中。
 * 时间复杂度 O(N)，其中 N 是链表的长度。空间复杂度 O(1)。
 */
class MergeNodesInBetweenZeros {

    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
        public ListNode mergeNodes(ListNode head) {
            ListNode dummy = new ListNode();
            ListNode tail = dummy;
            int total = 0;
            for (ListNode cur = head.next; cur != null; cur = cur.next) {
                if (cur.val == 0) {
                    ListNode node = new ListNode(total);
                    tail.next = node;
                    tail = tail.next;
                    total = 0;
                } else {
                    total += cur.val;
                }
            }

            return dummy.next;
        }

}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new MergeNodesInBetweenZeros().new Solution();
        ListNode head = ListNode.generalListNode(new int[]{0,3,1,0,4,5,2,0});
        ListNode listNode = solution.mergeNodes(head);
        ListNode.printListNode(listNode);
    }
}